package com.waiting.leetcode;

/**
 * @Description
 * @Author bjweitingting
 * @Date 2019/3/5
 **/
public class RegularExpressionMatching10 {
    private static final char star = '*';
    private static final char dot = '.';

    public boolean isMatch(String s, String p) {
        // initialize array to 1 length greater because we set 0,0 to true for empty.
        boolean[][] m = new boolean[s.length() + 1][p.length() + 1];

        // if string is empty and pattern is empty
        m[0][0] = true;

        // handle condition where pattern is a* or a*b* etc.
        for (int i = 1; i < m[0].length; i++) {
            if (p.charAt(i - 1) == star) {
                m[0][i] = m[0][i - 2];
            }
        }
        // since we start at index 1, i - 1 or j - 1 refers to current
        for (int i = 1; i < m.length; i++) {
            for (int j = 1; j < m[0].length; j++) {
                char text = s.charAt(i - 1);
                char pattern = p.charAt(j - 1);
                if (pattern == dot || pattern == text) {
                    // take the previous match value
                    m[i][j] = m[i - 1][j - 1];
                } else if (pattern == star) {
                    char prevPattern = p.charAt(j - 2);
                    // handle 0 occurences of text
                    m[i][j] = m[i][j - 2];
                    // if char before star is dot or char before star matches text
                    if (prevPattern == dot || prevPattern == text) {
                        m[i][j] = m[i][j] | m[i - 1][j];
                    }
                } else {
                    m[i][j] = false;
                }
            }
        }
        return m[s.length()][p.length()];
    }
}
